二項係数 nCkとMod（剰余算）
加法（＋），減法（ー），乗法（×）については，いつ行っても結果は同じ．
除法（÷）の代わりに逆元を使う．mod $ pのとき，$ aで割る代わりに，$ aの逆元である$ a^{p-2}を掛ける
2．二項係数
$ _nC_k= \frac{n!}{k!(n-k)!} なので，（値は整数だが）計算過程で割り算を含むので，剰余算では注意．
階乗$ n!の計算過程で値が大きくなりがち．Pythonにはきつい．MODをマメに使う必要あり．
（参考）Python 3.8から，math.comb(n, k)でも計算可能．でも数が大きくなると重くなるので注意
2.1 階乗 $ n!，$ 1/n!の逆元を求める漸化式
$ n!=1\cdot 2 \cdot 3\cdots nなので，$ O(n)で$ n!\ ({\rm mod}\ p)が求まる．
$ \frac1{n!}=\frac11\cdot \frac12 \cdot \frac13\cdots \frac1nなので，$ \frac1nの逆元が$ O(1)で求まれば，$ O(n)で$ \frac1{n!}\ ({\rm mod}\ p)が求まる．
2.2 逆数$ 1/nの逆元を求める漸化式
関係式 $ a^{-1} \equiv -(p \% a)^{-1} \times \lfloor p /a \rfloor\ ({\rm mod}\ p)を使う． 証明はこちら 2.3 $ _nC_kを求める
$ _nC_k = n!\ \cdot\ \left(\frac1{n!}\right)^{-1}\ \cdot\ \left(\frac1{(n-k)!}\right)^{-1}を使って求める．すべて掛け算で済むので，MOD計算も簡単．
code: python
M = 10000 # n! を求める最大の n
MOD = 998244353
# n!, 1/n, 1/n! をO(n)で計算
fact = 1 * (M + 1) # factn = (n! mod MOD) factinv = 1 * (M + 1) # factinvn = (mod MOD における n!の逆元) inv = 0 * (M + 1) # invn = (mod MOD における nの逆元) for i in range(2, M + 1):
invi = MOD - invMOD % i * (MOD // i) % MOD factinvi = factinvi - 1 * invi % MOD def comb(n, k):
return factn * factinvk * factinvn - k % MOD print(comb(10, 2)) # 10_C_2 = 45
参考サイト